home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / minix / libsrc~1.z / libsrc~1 / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-28  |  27.4 KB  |  1,240 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  *
  25.  *    The third parameter to regexec was added by Martin C. Atkins.
  26.  *    Andy Tanenbaum also made some changes.
  27.  */
  28.  
  29. #include <stdio.h>
  30. #include <regexp.h>
  31. #include <string.h>
  32. #include <sys/types.h>
  33. #include <unistd.h>
  34.  
  35. /*
  36.  * The first byte of the regexp internal "program" is actually this magic
  37.  * number; the start node begins in the second byte.
  38.  */
  39. #define    MAGIC    0234
  40.  
  41. /*
  42.  * The "internal use only" fields in regexp.h are present to pass info from
  43.  * compile to execute that permits the execute phase to run lots faster on
  44.  * simple cases.  They are:
  45.  *
  46.  * regstart    char that must begin a match; '\0' if none obvious
  47.  * reganch    is the match anchored (at beginning-of-line only)?
  48.  * regmust    string (pointer into program) that match must include, or NULL
  49.  * regmlen    length of regmust string
  50.  *
  51.  * Regstart and reganch permit very fast decisions on suitable starting points
  52.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  53.  * of lines that cannot possibly match.  The regmust tests are costly enough
  54.  * that regcomp() supplies a regmust only if the r.e. contains something
  55.  * potentially expensive (at present, the only such thing detected is * or +
  56.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  57.  * supplied because the test in regexec() needs it and regcomp() is computing
  58.  * it anyway.
  59.  */
  60.  
  61. /*
  62.  * Structure for regexp "program".  This is essentially a linear encoding
  63.  * of a nondeterministic finite-state machine (aka syntax charts or
  64.  * "railroad normal form" in parsing technology).  Each node is an opcode
  65.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  66.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  67.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  68.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  69.  * opposed to a collection of them) is never concatenated with anything
  70.  * because of operator precedence.)  The operand of some types of node is
  71.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  72.  * particular, the operand of a BRANCH node is the first node of the branch.
  73.  * (NB this is *not* a tree structure:  the tail of the branch connects
  74.  * to the thing following the set of BRANCHes.)  The opcodes are:
  75.  */
  76.  
  77. /* definition    number    opnd?    meaning */
  78. #define    END    0    /* no    End of program. */
  79. #define    BOL    1    /* no    Match "" at beginning of line. */
  80. #define    EOL    2    /* no    Match "" at end of line. */
  81. #define    ANY    3    /* no    Match any one character. */
  82. #define    ANYOF    4    /* str    Match any character in this string. */
  83. #define    ANYBUT    5    /* str    Match any character not in this string. */
  84. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  85. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  86. #define    EXACTLY    8    /* str    Match this string. */
  87. #define    NOTHING    9    /* no    Match empty string. */
  88. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  89. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  90. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  91.         /*    OPEN+1 is number 1, etc. */
  92. #define    CLOSE    30    /* no    Analogous to OPEN. */
  93.  
  94. /*
  95.  * Opcode notes:
  96.  *
  97.  * BRANCH    The set of branches constituting a single choice are hooked
  98.  *        together with their "next" pointers, since precedence prevents
  99.  *        anything being concatenated to any individual branch.  The
  100.  *        "next" pointer of the last BRANCH in a choice points to the
  101.  *        thing following the whole choice.  This is also where the
  102.  *        final "next" pointer of each individual branch points; each
  103.  *        branch starts with the operand node of a BRANCH node.
  104.  *
  105.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  106.  *        exists to make loop structures possible.
  107.  *
  108.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  109.  *        BRANCH structures using BACK.  Simple cases (one character
  110.  *        per match) are implemented with STAR and PLUS for speed
  111.  *        and to minimize recursive plunges.
  112.  *
  113.  * OPEN,CLOSE    ...are numbered at compile time.
  114.  */
  115.  
  116. /*
  117.  * A node is one char of opcode followed by two chars of "next" pointer.
  118.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  119.  * value is a positive offset from the opcode of the node containing it.
  120.  * An operand, if any, simply follows the node.  (Note that much of the
  121.  * code generation knows about this implicit relationship.)
  122.  *
  123.  * Using two bytes for the "next" pointer is vast overkill for most things,
  124.  * but allows patterns to get big without disasters.
  125.  */
  126. #define    OP(p)    (*(p))
  127. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  128. #define    OPERAND(p)    ((p) + 3)
  129.  
  130.  
  131.  
  132. /*
  133.  * Utility definitions.
  134.  */
  135. #ifndef CHARBITS
  136. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  137. #else
  138. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  139. #endif
  140.  
  141. #define    FAIL(m)    { regerror(m); return(NULL); }
  142. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  143. #define    META    "^$.[()|?+*\\"
  144.  
  145. /*
  146.  * Flags to be passed up and down.
  147.  */
  148. #define    HASWIDTH    01    /* Known never to match null string. */
  149. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  150. #define    SPSTART        04    /* Starts with * or +. */
  151. #define    WORST        0    /* Worst case. */
  152.  
  153. /*
  154.  * Global work variables for regcomp().
  155.  */
  156. static char *regparse;        /* Input-scan pointer. */
  157. static int regnpar;        /* () count. */
  158. static char regdummy;
  159. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  160. static long regsize;        /* Code size. */
  161.  
  162. /*
  163.  * Forward declarations for regcomp()'s friends.
  164.  */
  165. #ifndef STATIC
  166. #define    STATIC    static
  167. #endif
  168. STATIC char *reg();
  169. STATIC char *regbranch();
  170. STATIC char *regpiece();
  171. STATIC char *regatom();
  172. STATIC char *regnode();
  173. STATIC char *regnext();
  174. STATIC void regc();
  175. STATIC void reginsert();
  176. STATIC void regtail();
  177. STATIC void regoptail();
  178. #ifndef ATARI_ST
  179. STATIC int strcspn();
  180. #endif
  181.  
  182. /*
  183.  - regcomp - compile a regular expression into internal code
  184.  *
  185.  * We can't allocate space until we know how big the compiled form will be,
  186.  * but we can't compile it (and thus know how big it is) until we've got a
  187.  * place to put the code.  So we cheat:  we compile it twice, once with code
  188.  * generation turned off and size counting turned on, and once "for real".
  189.  * This also means that we don't allocate space until we are sure that the
  190.  * thing really will compile successfully, and we never have to move the
  191.  * code and thus invalidate pointers into it.  (Note that it has to be in
  192.  * one piece because free() must be able to free it all.)
  193.  *
  194.  * Beware that the optimization-preparation code in here knows about some
  195.  * of the structure of the compiled regexp.
  196.  */
  197. regexp *
  198. regcomp(exp)
  199. char *exp;
  200. {
  201.   register regexp *r;
  202.   register char *scan;
  203.   register char *longest;
  204.   register int len;
  205.   int flags;
  206. #ifdef ATARI_ST
  207. #ifdef __STDC__
  208.   _VOIDSTAR malloc(unsigned);
  209. #else
  210.   extern _VOIDSTAR malloc();
  211. #endif
  212. #else
  213.   extern char *malloc();
  214. #endif
  215.  
  216.   if (exp == NULL)
  217.     FAIL("NULL argument");
  218.  
  219.   /* First pass: determine size, legality. */
  220.   regparse = exp;
  221.   regnpar = 1;
  222.   regsize = 0L;
  223.   regcode = ®dummy;
  224.   regc(MAGIC);
  225.   if (reg(0, &flags) == NULL)
  226.     return(NULL);
  227.  
  228.   /* Small enough for pointer-storage convention? */
  229.   if (regsize >= 32767L)        /* Probably could be 65535L. */
  230.     FAIL("regexp too big");
  231.  
  232.   /* Allocate space. */
  233.   r = (regexp *)malloc((unsigned)(sizeof(regexp) + (unsigned)regsize));
  234.   if (r == NULL)
  235.     FAIL("out of space");
  236.  
  237.   /* Second pass: emit code. */
  238.   regparse = exp;
  239.   regnpar = 1;
  240.   regcode = r->program;
  241.   regc(MAGIC);
  242.   if (reg(0, &flags) == NULL)
  243.     return(NULL);
  244.  
  245.   /* Dig out information for optimizations. */
  246.   r->regstart = '\0';    /* Worst-case defaults. */
  247.   r->reganch = 0;
  248.   r->regmust = NULL;
  249.   r->regmlen = 0;
  250.   scan = r->program+1;            /* First BRANCH. */
  251.   if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  252.     scan = OPERAND(scan);
  253.  
  254.     /* Starting-point info. */
  255.     if (OP(scan) == EXACTLY)
  256.         r->regstart = *OPERAND(scan);
  257.     else if (OP(scan) == BOL)
  258.         r->reganch++;
  259.  
  260.     /*
  261.      * If there's something expensive in the r.e., find the
  262.      * longest literal string that must appear and make it the
  263.      * regmust.  Resolve ties in favor of later strings, since
  264.      * the regstart check works with the beginning of the r.e.
  265.      * and avoiding duplication strengthens checking.  Not a
  266.      * strong reason, but sufficient in the absence of others.
  267.      */
  268.     if (flags&SPSTART) {
  269.         longest = NULL;
  270.         len = 0;
  271.         for (; scan != NULL; scan = regnext(scan))
  272.             if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  273.                 longest = OPERAND(scan);
  274.                 len = strlen(OPERAND(scan));
  275.             }
  276.         r->regmust = longest;
  277.         r->regmlen = len;
  278.     }
  279.   }
  280.  
  281.   return(r);
  282. }
  283.  
  284. /*
  285.  - reg - regular expression, i.e. main body or parenthesized thing
  286.  *
  287.  * Caller must absorb opening parenthesis.
  288.  *
  289.  * Combining parenthesis handling with the base level of regular expression
  290.  * is a trifle forced, but the need to tie the tails of the branches to what
  291.  * follows makes it hard to avoid.
  292.  */
  293. static char *
  294. reg(paren, flagp)
  295. int paren;            /* Parenthesized? */
  296. int *flagp;
  297. {
  298.   register char *ret;
  299.   register char *br;
  300.   register char *ender;
  301.   register int parno;
  302.   int flags;
  303.  
  304.   *flagp = HASWIDTH;    /* Tentatively. */
  305.  
  306.   /* Make an OPEN node, if parenthesized. */
  307.   if (paren) {
  308.     if (regnpar >= NSUBEXP)
  309.         FAIL("too many ()");
  310.     parno = regnpar;
  311.     regnpar++;
  312.     ret = regnode(OPEN+parno);
  313.   } else
  314.     ret = NULL;
  315.  
  316.   /* Pick up the branches, linking them together. */
  317.   br = regbranch(&flags);
  318.   if (br == NULL)
  319.     return(NULL);
  320.   if (ret != NULL)
  321.     regtail(ret, br);    /* OPEN -> first. */
  322.   else
  323.     ret = br;
  324.   if (!(flags&HASWIDTH))
  325.     *flagp &= ~HASWIDTH;
  326.   *flagp |= flags&SPSTART;
  327.   while (*regparse == '|') {
  328.     regparse++;
  329.     br = regbranch(&flags);
  330.     if (br == NULL)
  331.         return(NULL);
  332.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  333.     if (!(flags&HASWIDTH))
  334.         *flagp &= ~HASWIDTH;
  335.     *flagp |= flags&SPSTART;
  336.   }
  337.  
  338.   /* Make a closing node, and hook it on the end. */
  339.   ender = regnode((paren) ? CLOSE+parno : END);    
  340.   regtail(ret, ender);
  341.  
  342.   /* Hook the tails of the branches to the closing node. */
  343.   for (br = ret; br != NULL; br = regnext(br))
  344.     regoptail(br, ender);
  345.  
  346.   /* Check for proper termination. */
  347.   if (paren && *regparse++ != ')') {
  348.     FAIL("unmatched ()");
  349.   } else if (!paren && *regparse != '\0') {
  350.     if (*regparse == ')') {
  351.         FAIL("unmatched ()");
  352.     } else
  353.         FAIL("junk on end");    /* "Can't happen". */
  354.     /* NOTREACHED */
  355.   }
  356.  
  357.   return(ret);
  358. }
  359.  
  360. /*
  361.  - regbranch - one alternative of an | operator
  362.  *
  363.  * Implements the concatenation operator.
  364.  */
  365. static char *
  366. regbranch(flagp)
  367. int *flagp;
  368. {
  369.   register char *ret;
  370.   register char *chain;
  371.   register char *latest;
  372.   int flags;
  373.  
  374.   *flagp = WORST;        /* Tentatively. */
  375.  
  376.   ret = regnode(BRANCH);
  377.   chain = NULL;
  378.   while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  379.     latest = regpiece(&flags);
  380.     if (latest == NULL)
  381.         return(NULL);
  382.     *flagp |= flags&HASWIDTH;
  383.     if (chain == NULL)    /* First piece. */
  384.         *flagp |= flags&SPSTART;
  385.     else
  386.         regtail(chain, latest);
  387.     chain = latest;
  388.   }
  389.   if (chain == NULL)    /* Loop ran zero times. */
  390.     (void) regnode(NOTHING);
  391.  
  392.   return(ret);
  393. }
  394.  
  395. /*
  396.  - regpiece - something followed by possible [*+?]
  397.  *
  398.  * Note that the branching code sequences used for ? and the general cases
  399.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  400.  * both the endmarker for their branch list and the body of the last branch.
  401.  * It might seem that this node could be dispensed with entirely, but the
  402.  * endmarker role is not redundant.
  403.  */
  404. static char *
  405. regpiece(flagp)
  406. int *flagp;
  407. {
  408.   register char *ret;
  409.   register char op;
  410.   register char *next;
  411.   int flags;
  412.  
  413.   ret = regatom(&flags);
  414.   if (ret == NULL)
  415.     return(NULL);
  416.  
  417.   op = *regparse;
  418.   if (!ISMULT(op)) {
  419.     *flagp = flags;
  420.     return(ret);
  421.   }
  422.  
  423.   if (!(flags&HASWIDTH) && op != '?')
  424.     FAIL("*+ operand could be empty");
  425.   *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  426.  
  427.   if (op == '*' && (flags&SIMPLE))
  428.     reginsert(STAR, ret);
  429.   else if (op == '*') {
  430.     /* Emit x* as (x&|), where & means "self". */
  431.     reginsert(BRANCH, ret);            /* Either x */
  432.     regoptail(ret, regnode(BACK));        /* and loop */
  433.     regoptail(ret, ret);            /* back */
  434.     regtail(ret, regnode(BRANCH));        /* or */
  435.     regtail(ret, regnode(NOTHING));        /* null. */
  436.   } else if (op == '+' && (flags&SIMPLE))
  437.     reginsert(PLUS, ret);
  438.   else if (op == '+') {
  439.     /* Emit x+ as x(&|), where & means "self". */
  440.     next = regnode(BRANCH);            /* Either */
  441.     regtail(ret, next);
  442.     regtail(regnode(BACK), ret);        /* loop back */
  443.     regtail(next, regnode(BRANCH));        /* or */
  444.     regtail(ret, regnode(NOTHING));        /* null. */
  445.   } else if (op == '?') {
  446.     /* Emit x? as (x|) */
  447.     reginsert(BRANCH, ret);            /* Either x */
  448.     regtail(ret, regnode(BRANCH));        /* or */
  449.     next = regnode(NOTHING);        /* null. */
  450.     regtail(ret, next);
  451.     regoptail(ret, next);
  452.   }
  453.   regparse++;
  454.   if (ISMULT(*regparse))
  455.     FAIL("nested *?+");
  456.  
  457.   return(ret);
  458. }
  459.  
  460. /*
  461.  - regatom - the lowest level
  462.  *
  463.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  464.  * it can turn them into a single node, which is smaller to store and
  465.  * faster to run.  Backslashed characters are exceptions, each becoming a
  466.  * separate node; the code is simpler that way and it's not worth fixing.
  467.  */
  468. static char *
  469. regatom(flagp)
  470. int *flagp;
  471. {
  472.   register char *ret;
  473.   int flags;
  474.  
  475.   *flagp = WORST;        /* Tentatively. */
  476.  
  477.   switch (*regparse++) {
  478.   case '^':
  479.     ret = regnode(BOL);
  480.     break;
  481.   case '$':
  482.     ret = regnode(EOL);
  483.     break;
  484.   case '.':
  485.     ret = regnode(ANY);
  486.     *flagp |= HASWIDTH|SIMPLE;
  487.     break;
  488.   case '[': {
  489.         register int class;
  490.         register int classend;
  491.  
  492.         if (*regparse == '^') {    /* Complement of range. */
  493.             ret = regnode(ANYBUT);
  494.             regparse++;
  495.         } else
  496.             ret = regnode(ANYOF);
  497.         if (*regparse == ']' || *regparse == '-')
  498.             regc(*regparse++);
  499.         while (*regparse != '\0' && *regparse != ']') {
  500.             if (*regparse == '-') {
  501.                 regparse++;
  502.                 if (*regparse == ']' || *regparse == '\0')
  503.                     regc('-');
  504.                 else {
  505.                     class = UCHARAT(regparse-2)+1;
  506.                     classend = UCHARAT(regparse);
  507.                     if (class > classend+1)
  508.                         FAIL("invalid [] range");
  509.                     for (; class <= classend; class++)
  510.                         regc(class);
  511.                     regparse++;
  512.                 }
  513.             } else
  514.                 regc(*regparse++);
  515.         }
  516.         regc('\0');
  517.         if (*regparse != ']')
  518.             FAIL("unmatched []");
  519.         regparse++;
  520.         *flagp |= HASWIDTH|SIMPLE;
  521.     }
  522.     break;
  523.   case '(':
  524.     ret = reg(1, &flags);
  525.     if (ret == NULL)
  526.         return(NULL);
  527.     *flagp |= flags&(HASWIDTH|SPSTART);
  528.     break;
  529.   case '\0':
  530.   case '|':
  531.   case ')':
  532.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  533.     break;
  534.   case '?':
  535.   case '+':
  536.   case '*':
  537.     FAIL("?+* follows nothing");
  538.     break;
  539.   case '\\':
  540.     if (*regparse == '\0')
  541.         FAIL("trailing \\");
  542.     ret = regnode(EXACTLY);
  543.     regc(*regparse++);
  544.     regc('\0');
  545.     *flagp |= HASWIDTH|SIMPLE;
  546.     break;
  547.   default: {
  548.         register int len;
  549.         register char ender;
  550.  
  551.         regparse--;
  552.         len = strcspn(regparse, META);
  553.         if (len <= 0)
  554.             FAIL("internal disaster");
  555.         ender = *(regparse+len);
  556.         if (len > 1 && ISMULT(ender))
  557.             len--;        /* Back off clear of ?+* operand. */
  558.         *flagp |= HASWIDTH;
  559.         if (len == 1)
  560.             *flagp |= SIMPLE;
  561.         ret = regnode(EXACTLY);
  562.         while (len > 0) {
  563.             regc(*regparse++);
  564.             len--;
  565.         }
  566.         regc('\0');
  567.     }
  568.     break;
  569.   }
  570.  
  571.   return(ret);
  572. }
  573.  
  574. /*
  575.  - regnode - emit a node
  576.  */
  577. static char *            /* Location. */
  578. regnode(op)
  579. char op;
  580. {
  581.   register char *ret;
  582.   register char *ptr;
  583.  
  584.   ret = regcode;
  585.   if (ret == ®dummy) {
  586.     regsize += 3;
  587.     return(ret);
  588.   }
  589.  
  590.   ptr = ret;
  591.   *ptr++ = op;
  592.   *ptr++ = '\0';        /* Null "next" pointer. */
  593.   *ptr++ = '\0';
  594.   regcode = ptr;
  595.  
  596.   return(ret);
  597. }
  598.  
  599. /*
  600.  - regc - emit (if appropriate) a byte of code
  601.  */
  602. static void
  603. regc(b)
  604. char b;
  605. {
  606.   if (regcode != ®dummy)
  607.     *regcode++ = b;
  608.   else
  609.     regsize++;
  610. }
  611.  
  612. /*
  613.  - reginsert - insert an operator in front of already-emitted operand
  614.  *
  615.  * Means relocating the operand.
  616.  */
  617. static void
  618. reginsert(op, opnd)
  619. char op;
  620. char *opnd;
  621. {
  622.   register char *src;
  623.   register char *dst;
  624.   register char *place;
  625.  
  626.   if (regcode == ®dummy) {
  627.     regsize += 3;
  628.     return;
  629.   }
  630.  
  631.   src = regcode;
  632.   regcode += 3;
  633.   dst = regcode;
  634.   while (src > opnd)
  635.     *--dst = *--src;
  636.  
  637.   place = opnd;        /* Op node, where operand used to be. */
  638.   *place++ = op;
  639.   *place++ = '\0';
  640.   *place++ = '\0';
  641. }
  642.  
  643. /*
  644.  - regtail - set the next-pointer at the end of a node chain
  645.  */
  646. static void
  647. regtail(p, val)
  648. char *p;
  649. char *val;
  650. {
  651.   register char *scan;
  652.   register char *temp;
  653.   register int offset;
  654.  
  655.   if (p == ®dummy)
  656.     return;
  657.  
  658.   /* Find last node. */
  659.   scan = p;
  660.   for (;;) {
  661.     temp = regnext(scan);
  662.     if (temp == NULL)
  663.         break;
  664.     scan = temp;
  665.   }
  666.  
  667.   if (OP(scan) == BACK)
  668.     offset = scan - val;
  669.   else
  670.     offset = val - scan;
  671.   *(scan+1) = (offset>>8)&0377;
  672.   *(scan+2) = offset&0377;
  673. }
  674.  
  675. /*
  676.  - regoptail - regtail on operand of first argument; nop if operandless
  677.  */
  678. static void
  679. regoptail(p, val)
  680. char *p;
  681. char *val;
  682. {
  683.   /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  684.   if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  685.     return;
  686.   regtail(OPERAND(p), val);
  687. }
  688.  
  689. /*
  690.  * regexec and friends
  691.  */
  692.  
  693. /*
  694.  * Global work variables for regexec().
  695.  */
  696. static char *reginput;        /* String-input pointer. */
  697. static char *regbol;        /* Beginning of input, for ^ check. */
  698. static char **regstartp;    /* Pointer to startp array. */
  699. static char **regendp;        /* Ditto for endp. */
  700.  
  701. /*
  702.  * Forwards.
  703.  */
  704. STATIC int regtry();
  705. STATIC int regmatch();
  706. STATIC int regrepeat();
  707.  
  708. #ifdef DEBUG
  709. int regnarrate = 0;
  710. void regdump();
  711. STATIC char *regprop();
  712. #endif
  713.  
  714. /*
  715.  - regexec - match a regexp against a string
  716.  */
  717. int
  718. regexec(prog, string, bolflag)
  719. register regexp *prog;
  720. register char *string;
  721. int bolflag;
  722. {
  723.   register char *s;
  724. #ifndef __STDC__    /* for __STDC__ pick up proto from <std.h> */
  725.   extern char *strchr();
  726. #endif
  727.  
  728.   /* Be paranoid... */
  729.   if (prog == NULL || string == NULL) {
  730.     regerror("NULL parameter");
  731.     return(0);
  732.   }
  733.  
  734.   /* Check validity of program. */
  735.   if (UCHARAT(prog->program) != MAGIC) {
  736.     regerror("corrupted program");
  737.     return(0);
  738.   }
  739.  
  740.   /* If there is a "must appear" string, look for it. */
  741.   if (prog->regmust != NULL) {
  742.     s = string;
  743.     while ((s = strchr(s, prog->regmust[0])) != NULL) {
  744.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  745.             break;    /* Found it. */
  746.         s++;
  747.     }
  748.     if (s == NULL)    /* Not present. */
  749.         return(0);
  750.   }
  751.  
  752.   /* Mark beginning of line for ^ . */
  753.   if(bolflag)
  754.     regbol = string;
  755.   else
  756.     regbol = NULL;
  757.  
  758.   /* Simplest case:  anchored match need be tried only once. */
  759.   if (prog->reganch)
  760.     return(regtry(prog, string));
  761.  
  762.   /* Messy cases:  unanchored match. */
  763.   s = string;
  764.   if (prog->regstart != '\0')
  765.     /* We know what char it must start with. */
  766.     while ((s = strchr(s, prog->regstart)) != NULL) {
  767.         if (regtry(prog, s))
  768.             return(1);
  769.         s++;
  770.     }
  771.   else
  772.     /* We don't -- general case. */
  773.     do {
  774.         if (regtry(prog, s))
  775.             return(1);
  776.     } while (*s++ != '\0');
  777.  
  778.   /* Failure. */
  779.   return(0);
  780. }
  781.  
  782. /*
  783.  - regtry - try match at specific point
  784.  */
  785. static int            /* 0 failure, 1 success */
  786. regtry(prog, string)
  787. regexp *prog;
  788. char *string;
  789. {
  790.   register int i;
  791.   register char **sp;
  792.   register char **ep;
  793.  
  794.   reginput = string;
  795.   regstartp = prog->startp;
  796.   regendp = prog->endp;
  797.  
  798.   sp = prog->startp;
  799.   ep = prog->endp;
  800.   for (i = NSUBEXP; i > 0; i--) {
  801.     *sp++ = NULL;
  802.     *ep++ = NULL;
  803.   }
  804.   if (regmatch(prog->program + 1)) {
  805.     prog->startp[0] = string;
  806.     prog->endp[0] = reginput;
  807.     return(1);
  808.   } else
  809.     return(0);
  810. }
  811.  
  812. /*
  813.  - regmatch - main matching routine
  814.  *
  815.  * Conceptually the strategy is simple:  check to see whether the current
  816.  * node matches, call self recursively to see whether the rest matches,
  817.  * and then act accordingly.  In practice we make some effort to avoid
  818.  * recursion, in particular by going through "ordinary" nodes (that don't
  819.  * need to know whether the rest of the match failed) by a loop instead of
  820.  * by recursion.
  821.  */
  822. static int            /* 0 failure, 1 success */
  823. regmatch(prog)
  824. char *prog;
  825. {
  826.   register char *scan;    /* Current node. */
  827.   char *next;        /* Next node. */
  828. #ifndef __STDC__    /* for __STDC__ pick up proto from <std.h> */
  829.   extern char *strchr();
  830. #endif
  831.  
  832.   scan = prog;
  833. #ifdef DEBUG
  834.   if (scan != NULL && regnarrate)
  835.     fprintf(stderr, "%s(\n", regprop(scan));
  836. #endif
  837.   while (scan != NULL) {
  838. #ifdef DEBUG
  839.     if (regnarrate)
  840.         fprintf(stderr, "%s...\n", regprop(scan));
  841. #endif
  842.     next = regnext(scan);
  843.  
  844.     switch (OP(scan)) {
  845.     case BOL:
  846.         if (reginput != regbol)
  847.             return(0);
  848.         break;
  849.     case EOL:
  850.         if (*reginput != '\0')
  851.             return(0);
  852.         break;
  853.     case ANY:
  854.         if (*reginput == '\0')
  855.             return(0);
  856.         reginput++;
  857.         break;
  858.     case EXACTLY: {
  859.             register int len;
  860.             register char *opnd;
  861.  
  862.             opnd = OPERAND(scan);
  863.             /* Inline the first character, for speed. */
  864.             if (*opnd != *reginput)
  865.                 return(0);
  866.             len = strlen(opnd);
  867.             if (len > 1 && strncmp(opnd, reginput, len) != 0)
  868.                 return(0);
  869.             reginput += len;
  870.         }
  871.         break;
  872.     case ANYOF:
  873.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  874.             return(0);
  875.         reginput++;
  876.         break;
  877.     case ANYBUT:
  878.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  879.             return(0);
  880.         reginput++;
  881.         break;
  882.     case NOTHING:
  883.         break;
  884.     case BACK:
  885.         break;
  886.     case OPEN+1:
  887.     case OPEN+2:
  888.     case OPEN+3:
  889.     case OPEN+4:
  890.     case OPEN+5:
  891.     case OPEN+6:
  892.     case OPEN+7:
  893.     case OPEN+8:
  894.     case OPEN+9: {
  895.             register int no;
  896.             register char *save;
  897.  
  898.             no = OP(scan) - OPEN;
  899.             save = reginput;
  900.  
  901.             if (regmatch(next)) {
  902.                 /*
  903.                  * Don't set startp if some later
  904.                  * invocation of the same parentheses
  905.                  * already has.
  906.                  */
  907.                 if (regstartp[no] == NULL)
  908.                     regstartp[no] = save;
  909.                 return(1);
  910.             } else
  911.                 return(0);
  912.         }
  913.         break;
  914.     case CLOSE+1:
  915.     case CLOSE+2:
  916.     case CLOSE+3:
  917.     case CLOSE+4:
  918.     case CLOSE+5:
  919.     case CLOSE+6:
  920.     case CLOSE+7:
  921.     case CLOSE+8:
  922.     case CLOSE+9: {
  923.             register int no;
  924.             register char *save;
  925.  
  926.             no = OP(scan) - CLOSE;
  927.             save = reginput;
  928.  
  929.             if (regmatch(next)) {
  930.                 /*
  931.                  * Don't set endp if some later
  932.                  * invocation of the same parentheses
  933.                  * already has.
  934.                  */
  935.                 if (regendp[no] == NULL)
  936.                     regendp[no] = save;
  937.                 return(1);
  938.             } else
  939.                 return(0);
  940.         }
  941.         break;
  942.     case BRANCH: {
  943.             register char *save;
  944.  
  945.             if (OP(next) != BRANCH)        /* No choice. */
  946.                 next = OPERAND(scan);    /* Avoid recursion. */
  947.             else {
  948.                 do {
  949.                     save = reginput;
  950.                     if (regmatch(OPERAND(scan)))
  951.                         return(1);
  952.                     reginput = save;
  953.                     scan = regnext(scan);
  954.                 } while (scan != NULL && OP(scan) == BRANCH);
  955.                 return(0);
  956.                 /* NOTREACHED */
  957.             }
  958.         }
  959.         break;
  960.     case STAR:
  961.     case PLUS: {
  962.             register char nextch;
  963.             register int no;
  964.             register char *save;
  965.             register int min;
  966.  
  967.             /*
  968.              * Lookahead to avoid useless match attempts
  969.              * when we know what character comes next.
  970.              */
  971.             nextch = '\0';
  972.             if (OP(next) == EXACTLY)
  973.                 nextch = *OPERAND(next);
  974.             min = (OP(scan) == STAR) ? 0 : 1;
  975.             save = reginput;
  976.             no = regrepeat(OPERAND(scan));
  977.             while (no >= min) {
  978.                 /* If it could work, try it. */
  979.                 if (nextch == '\0' || *reginput == nextch)
  980.                     if (regmatch(next))
  981.                         return(1);
  982.                 /* Couldn't or didn't -- back up. */
  983.                 no--;
  984.                 reginput = save + no;
  985.             }
  986.             return(0);
  987.         }
  988.         break;
  989.     case END:
  990.         return(1);    /* Success! */
  991.         break;
  992.     default:
  993.         regerror("memory corruption");
  994.         return(0);
  995.         break;
  996.     }
  997.  
  998.     scan = next;
  999.   }
  1000.  
  1001.   /*
  1002.    * We get here only if there's trouble -- normally "case END" is
  1003.    * the terminating point.
  1004.    */
  1005.   regerror("corrupted pointers");
  1006.   return(0);
  1007. }
  1008.  
  1009. /*
  1010.  - regrepeat - repeatedly match something simple, report how many
  1011.  */
  1012. static int
  1013. regrepeat(p)
  1014. char *p;
  1015. {
  1016.   register int count = 0;
  1017.   register char *scan;
  1018.   register char *opnd;
  1019.  
  1020.   scan = reginput;
  1021.   opnd = OPERAND(p);
  1022.   switch (OP(p)) {
  1023.   case ANY:
  1024.     count = strlen(scan);
  1025.     scan += count;
  1026.     break;
  1027.   case EXACTLY:
  1028.     while (*opnd == *scan) {
  1029.         count++;
  1030.         scan++;
  1031.     }
  1032.     break;
  1033.   case ANYOF:
  1034.     while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1035.         count++;
  1036.         scan++;
  1037.     }
  1038.     break;
  1039.   case ANYBUT:
  1040.     while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1041.         count++;
  1042.         scan++;
  1043.     }
  1044.     break;
  1045.   default:        /* Oh dear.  Called inappropriately. */
  1046.     regerror("internal foulup");
  1047.     count = 0;    /* Best compromise. */
  1048.     break;
  1049.   }
  1050.   reginput = scan;
  1051.  
  1052.   return(count);
  1053. }
  1054.  
  1055. /*
  1056.  - regnext - dig the "next" pointer out of a node
  1057.  */
  1058. static char *
  1059. regnext(p)
  1060. register char *p;
  1061. {
  1062.   register int offset;
  1063.  
  1064.   if (p == ®dummy)
  1065.     return(NULL);
  1066.  
  1067.   offset = NEXT(p);
  1068.   if (offset == 0)
  1069.     return(NULL);
  1070.  
  1071.   if (OP(p) == BACK)
  1072.     return(p-offset);
  1073.   else
  1074.     return(p+offset);
  1075. }
  1076.  
  1077. #ifdef DEBUG
  1078.  
  1079. STATIC char *regprop();
  1080.  
  1081. /*
  1082.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1083.  */
  1084. void
  1085. regdump(r)
  1086. regexp *r;
  1087. {
  1088.   register char *s;
  1089.   register char op = EXACTLY;    /* Arbitrary non-END op. */
  1090.   register char *next;
  1091. #ifndef __STDC__    /* for __STDC__ pick up proto from <std.h> */
  1092.   extern char *strchr();
  1093. #endif
  1094.  
  1095.   s = r->program + 1;
  1096.   while (op != END) {    /* While that wasn't END last time... */
  1097.     op = OP(s);
  1098.     printf("%2d%s", (int)(s-r->program), regprop(s));    /* Where, what. */
  1099.     next = regnext(s);
  1100.     if (next == NULL)        /* Next ptr. */
  1101.         printf("(0)");
  1102.     else 
  1103.         printf("(%d)", (int)(s-r->program)+(int)(next-s));
  1104.     s += 3;
  1105.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1106.         /* Literal string, where present. */
  1107.         while (*s != '\0') {
  1108.             putchar(*s);
  1109.             s++;
  1110.         }
  1111.         s++;
  1112.     }
  1113.     putchar('\n');
  1114.   }
  1115.  
  1116.   /* Header fields of interest. */
  1117.   if (r->regstart != '\0')
  1118.     printf("start `%c' ", r->regstart);
  1119.   if (r->reganch)
  1120.     printf("anchored ");
  1121.   if (r->regmust != NULL)
  1122.     printf("must have \"%s\"", r->regmust);
  1123.   printf("\n");
  1124. }
  1125.  
  1126. /*
  1127.  - regprop - printable representation of opcode
  1128.  */
  1129. static char *
  1130. regprop(op)
  1131. char *op;
  1132. {
  1133.   register char *p;
  1134.   static char buf[50];
  1135.  
  1136.   (void) strcpy(buf, ":");
  1137.  
  1138.   switch (OP(op)) {
  1139.   case BOL:
  1140.     p = "BOL";
  1141.     break;
  1142.   case EOL:
  1143.     p = "EOL";
  1144.     break;
  1145.   case ANY:
  1146.     p = "ANY";
  1147.     break;
  1148.   case ANYOF:
  1149.     p = "ANYOF";
  1150.     break;
  1151.   case ANYBUT:
  1152.     p = "ANYBUT";
  1153.     break;
  1154.   case BRANCH:
  1155.     p = "BRANCH";
  1156.     break;
  1157.   case EXACTLY:
  1158.     p = "EXACTLY";
  1159.     break;
  1160.   case NOTHING:
  1161.     p = "NOTHING";
  1162.     break;
  1163.   case BACK:
  1164.     p = "BACK";
  1165.     break;
  1166.   case END:
  1167.     p = "END";
  1168.     break;
  1169.   case OPEN+1:
  1170.   case OPEN+2:
  1171.   case OPEN+3:
  1172.   case OPEN+4:
  1173.   case OPEN+5:
  1174.   case OPEN+6:
  1175.   case OPEN+7:
  1176.   case OPEN+8:
  1177.   case OPEN+9:
  1178.     sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1179.     p = NULL;
  1180.     break;
  1181.   case CLOSE+1:
  1182.   case CLOSE+2:
  1183.   case CLOSE+3:
  1184.   case CLOSE+4:
  1185.   case CLOSE+5:
  1186.   case CLOSE+6:
  1187.   case CLOSE+7:
  1188.   case CLOSE+8:
  1189.   case CLOSE+9:
  1190.     sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1191.     p = NULL;
  1192.     break;
  1193.   case STAR:
  1194.     p = "STAR";
  1195.     break;
  1196.   case PLUS:
  1197.     p = "PLUS";
  1198.     break;
  1199.   default:
  1200.     regerror("corrupted opcode");
  1201.     break;
  1202.   }
  1203.   if (p != NULL)
  1204.     (void) strcat(buf, p);
  1205.   return(buf);
  1206. }
  1207. #endif
  1208.  
  1209. #ifndef ATARI_ST
  1210. /*
  1211.  * The following is provided for those people who do not have strcspn() in
  1212.  * their C libraries.  They should get off their butts and do something
  1213.  * about it; at least one public-domain implementation of those (highly
  1214.  * useful) string routines has been published on Usenet.
  1215.  */
  1216. /*
  1217.  * strcspn - find length of initial segment of s1 consisting entirely
  1218.  * of characters not from s2
  1219.  */
  1220.  
  1221. static int
  1222. strcspn(s1, s2)
  1223. char *s1;
  1224. char *s2;
  1225. {
  1226.   register char *scan1;
  1227.   register char *scan2;
  1228.   register int count;
  1229.  
  1230.   count = 0;
  1231.   for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1232.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1233.         if (*scan1 == *scan2++)
  1234.             return(count);
  1235.     count++;
  1236.   }
  1237.   return(count);
  1238. }
  1239. #endif
  1240.